package Algorithm.DynamicPlanning;

public class Code10_PalindromeMinCut {

    public static int minCut(String str){
        if (str == null || str.length() == 0){
            return 0;
        }
        char[] chas = str.toCharArray();
        int len = chas.length;
        int[] dp = new int[len + 1];
        dp[len] = 0;
        dp[len - 1] = 1; // 在最后一个字符，自己是回文串，最多分成一部分
        boolean[][] p = record(chas); // 把[i……j]是否是回文串记录下来
        // 计算dp
        for (int i = len - 2; i >= 0; i--) { // 右向左递推
            dp[i] = chas.length - i; // 初始化[i,最后]，最多分成几部分
            for (int j = i; j < len; j++){
                if (p[i][j]){
                    dp[i] = Math.min(dp[i], dp[j + 1] + 1);
                }
            }
        }
        return dp[0]; // 返回[0,……，str.length-1]最少能分成几部分
    }

    public static boolean[][] record(char[] str){
        boolean[][] record = new boolean[str.length][str.length];
        record[str.length - 1][str.length - 1] = true;
        for (int i = 0; i < str.length - 1; i++) {
            record[i][i] = true;
            record[i][i + 1] = (str[i] == str[i + 1]);
        }
        // 填普遍位置
        for (int i = str.length - 3; i >= 0; i--) {
            for (int j = i + 2; j < str.length; j++){
                // (L+1,……R-1)是回文串，并且i,j对应字符相同
                record[i][j] = (record[i + 1][j - 1] && str[i] == str[j]);
            }
        }
        return record;
    }

    public static void main(String[] args) {
        String str = "ACDCDCDAD";
        System.out.println(minCut(str) - 1);
    }
}
